﻿using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using System;
using System.Text;
using System.IO;

namespace Utility.DataStructure.Octree
{
	public class Octree<T>
	{
		public OctreeNode<T> Root { get; protected set; }

		public Octree ()
		{
			Root = OctreeNode<T>.NewRoot ();
		}

		void GetLeafNodes (OctreeNode<T> node, List<OctreeNode<T>> list)
		{
			if (node.IsLeaf)
			{
				list.Add (node);
			}

			for (int i = 0; i < 8; i++)
			{
				GetLeafNodes (node[i], list);
			}
		}

		public List<OctreeNode<T>> GetLeafNodes (List<OctreeNode<T>> list = null)
		{
			if (list == null)
			{
				list = new List<OctreeNode<T>> ();
			}
			else
			{
				list.Clear ();
			}

			GetLeafNodes (Root, list);
			return list;
		}

		void GetLeafNodeInfos (OctreeNode<T> node, List<NodeInfo<T>> list)
		{
			if (node.IsLeaf)
			{
				list.Add (node.GetInfo ());
			}
			else
			{
				for (int i = 0; i < 8; i++)
				{
					GetLeafNodeInfos (node[i], list);
				}
			}
		}

		public List<NodeInfo<T>> GetLeafNodeInfos (List<NodeInfo<T>> list = null)
		{
			if (list == null)
			{
				list = new List<NodeInfo<T>> ();
			}
			else
			{
				list.Clear ();
			}

			GetLeafNodeInfos (Root, list);
			return list;
		}

		static StringBuilder builder;
		public string GetTreeDebugString ()
		{
			builder = builder ?? new StringBuilder ();
			BuildNodeString (builder, Root, "");
			string str = builder.ToString ();
			builder.Clear ();
			return str;
		}

		void BuildNodeString (StringBuilder builder, OctreeNode<T> node, string parentId, string indent = null)
		{
			indent = indent == null ? "" : indent + "    ";
			parentId = parentId == "" ? "T" : string.Format ("{0}_{1}", parentId, node.OctantId);
			string str = string.Format ("[{0}]  Data: {1}", parentId, node.Data.ToString ());
			builder.AppendLine (indent + str);
			if (!node.IsLeaf)
			{
				for (int i = 0; i < 8; i++)
				{
					BuildNodeString (builder, node[i], parentId, indent);
				}
			}
		}
		#region serialization
		protected virtual void WriteData (T data, BinaryWriter writer)
		{
			throw new NotImplementedException ();
		}

		protected virtual T ReadData (BinaryReader reader)
		{
			throw new NotImplementedException ();
		}

		void WriteNode (OctreeNode<T> node, BinaryWriter writer, Queue<OctreeNode<T>> queue)
		{
			//write voxel data
			WriteData (node.Data, writer);
			//is have child nodes
			if (!node.IsLeaf)
			{
				//indicate which of the child nodes are leaf
				byte flags = 0;
				for (int i = 0; i < 8; i++)
				{
					var child = node[i];
					var flag = (byte)(Convert.ToByte (child.IsLeaf) << i);
					flags |= flag;

					//enqueue
					queue.Enqueue (child);
				}
				writer.Write (flags);
			}
		}

		public void Serialize (BinaryWriter writer, Queue<OctreeNode<T>> queue = null)
		{
			queue = queue ?? new Queue<OctreeNode<T>> ();
			queue.Clear ();

			//write root is leaf or not
			writer.Write (Root.IsLeaf);
			WriteNode (Root, writer, queue);

			while (queue.Count > 0)
			{
				WriteNode (queue.Dequeue (), writer, queue);
			}
		}

		void ReadNode (OctreeNode<T> node, BinaryReader reader, Queue<OctreeNode<T>> queue)
		{
			node.Data = ReadData (reader);
			if (!node.IsLeaf)
			{
				byte flags = reader.ReadByte ();
				for (int i = 0; i < 8; i++)
				{
					var child = node[i];
					bool isLeaf = Convert.ToBoolean (flags & (1 << i));
					PrepareNode (child, isLeaf);
					queue.Enqueue (child);
				}
			}
		}

		void PrepareNode (OctreeNode<T> node, bool isLeaf)
		{
			if (isLeaf)
			{
				node.ClearChilds ();
			}
			else
			{
				if (node.IsLeaf)
				{
					node.Divide ();
				}
			}
		}

		public void Deserialize (BinaryReader reader, Queue<OctreeNode<T>> queue = null)
		{
			queue = queue ?? new Queue<OctreeNode<T>> ();
			queue.Clear ();

			bool rootIsLeaf = reader.ReadBoolean ();
			PrepareNode (Root, rootIsLeaf);
			ReadNode (Root, reader, queue);

			while (queue.Count > 0)
			{
				ReadNode (queue.Dequeue (), reader, queue);
			}
		}
		#endregion
	}


}